package com.yeban.algorithm;

/**
 * @Desc TODO
 * @Author yeban
 * @Date 2025/10/29
 * 37.解数独
 */
public class test37 {

    boolean[][] rowsUsed = new boolean[9][10];
    boolean[][] colsUsed = new boolean[9][10];
    boolean[][] boxsUsed = new boolean[9][10];

    public void solveSudoku(char[][] board) {
        // 初始化标记
        for(int i = 0; i < 9; i ++) {
            for(int j = 0; j < 9; j ++) {
                char c = board[i][j];
                if(c != '.') {
                    int d = c - '0';
                    rowsUsed[i][d] = true;
                    colsUsed[j][d] = true;
                    boxsUsed[getBoxIndex(i,j)][d] = true;
                }
            }
        }

        backTrack(board, 0, 0);
    }

    public boolean backTrack(char[][] board, int row, int col) {
        if(row == 9) {
            return true;
        }

        // 到达一行末尾，换行
        if(col == 9) {
            return backTrack(board, row+1, 0);
        }

        // 当前行有数字，跳过
        if(board[row][col] != '.') {
            return backTrack(board, row, col+1);
        }

        // 遍历1-9
        for(int num = 1; num <= 9; num ++) {
            int boxIndex = getBoxIndex(row, col);
            if(!rowsUsed[row][num] && !colsUsed[col][num] && !boxsUsed[boxIndex][num]) {

                // 放置数字
                board[row][col] = (char)(num + '0');
                rowsUsed[row][num] = colsUsed[col][num] = boxsUsed[boxIndex][num] = true;

                // 递归下一个数字
                if(backTrack(board, row, col+1)) {
                    return true;
                }

                // 回溯撤销
                board[row][col] = '.';
                rowsUsed[row][num] = colsUsed[col][num] = boxsUsed[boxIndex][num] = false;
            }
        }
        return false;
    }

    private int getBoxIndex(int row, int col) {
        return (row / 3) * 3 + (col / 3);
    }
}
